This invention pertains to the compression of images for transmission over networks and their reconstruction upon reception. In particular, it pertains to the compression and reconstruction of image signals using inter-block correlation and a layered addressing structure to form variable block sizes to increase compression and reduce bit rate.
Vector quantization has been applied to speech coding for a number of years. However, the application of vector quantization to image coding is relatively new. Vector quantization for reducing bit-rate has been found to be a very efficient technique due to its inherent ability to exploit correlation between neighboring pixels. Vector quantization has been applied both in the spatial and transformed domain in various forms. In its basic form, as illustrated in the block diagram of FIG. 1, an image is divided into blocks of N.times.N pixels. In the transmitter and receiver identical code books 15 exist whose entries contain combinations of pixels in a block 31 (FIG. 6). Assuming that there are M shades of gray in an image, theoretically, (M).sup.N.times.N combinations are possible. In practice, however, there are only a limited number of combinations that occur most often, which reduces the size of the code table or code book considerably. The code book is created by training it over a large set of test images of different types. During the coding process, each block of the actual image 10, being compressed is compared 12 with entries 14 in the code book 15, and the address of that entry, which best matches using the nearest neighbor rule, the image being compressed or encoded is transmitted 16 to the receiver. On the receive side, the received address is used to fetch 17 the same block 14 from the code book 15, which is then used to reconstruct the image 19. Typical block 14 and code book 15 sizes that are used are 4.times.4 and 256, respectively. Since it takes 8 bits to address an entry in the code book, a compression factor of 16 or bit rate of 0.5 bit per pixel is achieved, assuming that the original image is made up of 256 shades of gray. U.S. Pat. No. 4,797,739 issued to Tanaka is representative of the prior art.
Two major problems of vector quantization are: how to design a good code book that is representative of all the possible occurrences of pixel combinations in a block, and how to find a best match in the code book during the coding process. Some researchers have suggested various clustering techniques to design good code books. Tree searched algorithms have been used to speed up the code vector search process. A good overview of vector quantization can be found in Gray, IEEE ASSP Magazine, Apr. 1984, pp. 4-29. This invention does not relate to either the code table design or the search process. Rather, it deals with how we can exploit inter-block correlation to design variable block size vector quantization, and how to structure the code tables in an inter-related manner to further increase compression.
Traditional approaches to vector quantization rely on partitioning an image into blocks of equal size to exploit correlation between neighboring pixels. This concept can be further extended to inter-block correlation to design variable block size vector quantization. Vaisey and Gersho have published a variable block size coding technique, in which a 32.times.32 block is tested to determine if it should be further subdivided into 4 blocks of 16.times.16. Again, the 16 .times.16 blocks are subdivided into four 8.times.8 blocks if certain conditions are not met, and this process continues until it is not necessary to further subdivide the blocks or the basic block size of 4.times.4 is reached. The decision to generate (or not to generate) 4 children is made by the following process: assuming that an N.times.N block is being tested, first the pixel mean is calculated in the block and the corresponding quantized pixel mean is subtracted from each pixel in the block to produce a residual block. Then, the variance of the pixels in the block is calculated, and if this variance exceeds a pre-set threshold, then the block is subdivided to generate 4 children; else, we code the block as it is. Thus, the large block is described by two quad-trees: the detail tree and the mean tree. The detail tree provides the segmentation information. The residual blocks of size 32.times.32, 16.times.16, and 8.times.8 blocks are first transform coded, then vector coded using the corresponding code tables. Residual blocks of size 4.times.4 are vector coded directly (in the spatial domain). The major problems of this technique are: need to send detail and mean tree side information, complex segmentation process, use of several code tables, and need to do block transform. Daly and Hsing have reported using large blocks of 16.times.16, then subdividing them into four children based on a detail criteria, and so on, until either the detail test is met or the basic block size of 2.times.2 is reached. There are four different code tables, one for each block size. So, this technique is basically straightforward, but intensive in terms of computing and memory requirements.
Feng and Nasrabadi "A new vector quantization scheme using interblock correlation: address-vector quantizer", Proc. GlobeCom, Ft. Lauderdale, Fla. 1988 have proposed an address-vector quantizer where four basic blocks are combined into one larger block, and are coded by using an address code book. The address code book consists of a set of address code vectors where each address code vector represents a combination of blocks, and each of its elements represents address of an entry in the code book designed for the basic block vectors. The address code book itself is very large, and is divided into active and passive sections.